package io.github.hadyang.leetcode.offer;

import java.util.ArrayList;
import java.util.LinkedList;
import org.junit.Test;

/** @author haoyang.shi */
public class MaxInWindows {

  @Test
  public void test() {
    System.out.println(maxInWindows(new int[] {2, 3, 4, 2, 6, 2, 5, 1}, 3));
    System.out.println(maxInWindows(new int[] {1, 3, 5, 7, 9, 11, 13, 15}, 4));
  }

  public ArrayList<Integer> maxInWindows(int[] num, int size) {
    ArrayList<Integer> res = new ArrayList<>();

    if (size == 0) return res;

    LinkedList<Integer> queue = new LinkedList<>();

    for (int i = 0; i < num.length; i++) {
      while (queue.peekFirst() != null && i - queue.peekFirst() >= size) {
        queue.removeFirst();
      }

      while (queue.peekLast() != null && i - queue.peekLast() >= size) {
        queue.removeLast();
      }

      if (queue.isEmpty()) {
        queue.addFirst(i);
      } else {
        if (num[i] > num[queue.peekFirst()]) {
          queue.clear();
          queue.addFirst(i);
        } else {
          while (num[i] > num[queue.peekLast()]) {
            queue.removeLast();
          }
          queue.addLast(i);
        }
      }

      if (i >= size - 1) res.add(num[queue.peekFirst()]);
    }

    return res;
  }
}
